/*
 * @Author: your name
 * @Date: 2021-07-22 18:22:48
 * @LastEditTime: 2021-07-22 19:48:29
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \2_线性表\死锁检测算法.cpp
 */
#include <iostream>
using namespace std;
int main()
{
    cout << "===========程序开始执行=====================\n";
    //定义数据结构并获取当前状态
    int m, n; //资源的种类、进程的数目
    cout << "请输入资源的种类：";
    cin >> m;
    cout << "请输入进程的数目：";
    cin >> n;
    int Available[m];     //可利用资源向量
    int Allocation[n][m]; //分配矩阵
    int Request[n][m];    //请求矩阵
    int Work[m];          //工作向量
    int Finish[m] = {0};  //进程向量，初值置为0
    //读入可用资源数
    cout << "请输入系统可提供的各种资源的数量(用空格隔开):";
    for (int i = 0; i < m; i++)
    {
        cin >> Available[i];
    }
    //进程当前对各类资源的请求数目
    cout << "\n请输入进程当前对各类资源的请求数目\n";
    for (int i = 0; i < n; i++)
    {
        cout << "请输入进程P" << i << "当前对各类资源的请求数目（用空格隔开):";
        for (int j = 0; j < m; j++)
        {
            cin >> Request[i][j];
        }
    }
    //读入进程已分配各种资源的数目
    cout << "\n请输入进程已分配各种资源的数目\n";
    for (int i = 0; i < n; i++)
    {
        cout << "请输入进程P" << i << "已分配各种资源的数量（用空格隔开):";
        for (int j = 0; j < m; j++)
        {
            cin >> Allocation[i][j];
        }
    }

    //检测算法
    //Work=Available
    for (int i = 0; i < m; i++)
    {
        Work[i] = Available[i];
    }
    //不占用资源的进程计入Finish中，对应下标的单元置为1
    int count = 0; //计算不占用资源的进程的个数
    for (int i = 0; i < n; i++)
    {
        int flag = 0;
        for (int j = 0; j < m; j++)
        {
            if (Allocation[i][j] != 0 || Request[i][j] != 0)
            {
                flag = 1;
                break;
            }
        }
        if (flag == 0)
        {
            Finish[i] = 1; //不占资源的进程记录在Finish向量中
            count++;       //计算器加一
        }
    }

    //对所有拥有资源的进程，尝试将其化简
    for (int k = 0; k < n - count; k++)
    {
        for (int i = 0; i < n; i++)
        {
            int flag = 0;
            if (Finish[i] == 0)
            {
                for (int j = 0; j < m; j++)
                { //测试是否Request<=Work
                    if (Request[i][j] > Work[j])
                    {
                        flag = 1;
                        break;
                    }
                }
                if (flag == 0)
                { //化简，收回所有边
                    for (int j = 0; j < m; j++)
                    {
                        Work[j] = Work[j] + Allocation[i][j];
                    }
                    Finish[i] = 1; //记入在Finish向量中
                }
            }
        }
    }

    //判断是否所有进程都被回收
    int flag = 0;
    for (int i = 0; i < n - 1; i++)
    {
        if (Finish[i] == 0)
        {
            flag = 1;
            break;
        }
    }

    //输出结果并终止导致死锁的进程
    if (flag == 0)
    {
        cout << "\n该系统不会发生死锁！";
    }
    else
    {
        cout << "\n该系统会发生死锁！即将终止导致死锁的进程以解除死锁！\n";
        //回收资源,终止进程
        for (int i = 0; i < n; i++)
        {
            if (Finish[i] == 0)
            {
                for (int j = 0; j < m; j++)
                {
                    Available[j] = Available[j] + Allocation[i][j];
                    Allocation[i][j] = 0;
                    Request[i][j] = 0;
                }
                cout << "进程p" << i << "已被终止！\n";
            }
        }
        //输出终止后系统状态
        cout << "\n=====当前系统状态=====\n";
        cout << "当前系统可利用资源Available=(";
        for (int i = 0; i < m; i++)
        {
            cout << Available[i] << " ";
        }
        cout << ")\n";
        cout << "当前存在进程:P=( ";
        for (int i = 0; i < n; i++)
        {
            if (Finish[i] == 1)
            {
                cout << "P" << i << " ";
            }
        }
        cout << ")\n";
    }
}
